package 单周赛.history;

import java.util.HashSet;
import java.util.Set;

/**
 *
 */
public class 第330场单周赛 {

    public static void main(String[] args) {

//        System.out.println(distinctIntegers(3));

        System.out.println(monkeyMove(500000003));

    }

    public static int distinctIntegers(int n) {
        Set<Integer> set = new HashSet<>();
        set.add(n);

        for (int j = 0; j < 109; j++) {
            Set<Integer> curSet = new HashSet<>();
            for (int i = 1; i <= n; i++) {
                for (Integer x : set) {
                    if (x % i == 1) {
                        curSet.add(i);
                    }
                }
            }
            set.addAll(curSet);
        }
        return set.size();
    }

    /**
     * 逆向思维+快速幂
     * 1，每个猴子可以选择顺时针，逆时针 2 种方案，根据乘法原理
     * 一共有 n 个猴子，那么总方案数为，2 的 n 次幂
     * 不会发生一次碰撞有 2 种方案，所有猴子顺时针跳，或者所有
     * 猴子逆时针跳
     * 那么答案即为 所有方案数 - 2 = 发生碰撞的方案数
     * 2，由于 n 比较大，可以用快速幂降低求 2 的 n 次幂对
     * 1000000007 取模的值的时间复杂度
     */
    public static int monkeyMove(int n) {
        return (int) fastPower(2, n) - 2;
    }

    private static int mod = 1000000007;

    public static long fastPower(long a, long b) {
        if (b == 1) {
            return a;
        }

        long ans = fastPower((a * a - 2) % mod + 2, b >> 1);
        if ((b & 1) == 1) {
            ans = (ans * a - 2) % mod + 2;
        }
        return ans;
    }

}
